package Exerise;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test1 {
    /*给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

    请注意 ，必须在不复制数组的情况下原地对数组进行操作*/
    public void moveZeroes(int[] nums) {
        if(nums==null){
            return ;
        }
        int len = nums.length;
        int j=0;
        for (int i=0;i<len;++i){
            if(nums[i]!=0){
                int tmp = nums[j];
                nums[i] =nums[j];
                nums[j++] = tmp;
            }
        }
    }



    /*给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

    你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

    你可以按任意顺序返回答案*/
    public int[] twoSum(int[] nums, int target) {
        int len =nums.length;
        for (int i = 0; i < len; i++) {
           for (int j=i+1;j<len;j++){
               if(nums[i]+nums[j]==target){
                   return  new int[] {i,j};
               }
           }
        }
        return new int[0];
    }
    //移除元素
    public int removeElement(int[] nums, int val) {
        int cur =nums.length;
        for(int i=0;i<cur;){
            if(cur==val){
                nums[i] =nums[cur-1];
                cur--;
            }else {
                i++;
            }
        }
        return cur;
    }
    //方法1
    public int removeElement1(int[] nums, int val) {
        int key =0;
        for(int num:nums){
            if(val !=key){
               nums[key] = num;
                key++;
            }
        }
        return key;
    }
    //给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    //请必须使用时间复杂度为 O(log n) 的算法
    //使用了二分查找
    public int searchInsert(int[] nums, int target) {
        int left =0;
        int right =nums.length;
        while(left<=right){
            int mid = (left+right)/2;
            if(mid==target){
                return mid;
            }else if(mid<target){
                return mid+1;
            }else{
                return mid-1;
            }
        }
        return left;
    }

    public static void main1(String[] args) {
        int [] arr={1,2,3,4,5};
        System.out.println(arr.length);
        System.out.println(arr[1]);
    }
    /*给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。*/
    public int[] plusOne(int[] digits) {
        int len =digits.length;
        for (int i = len-1; i >=0 ; i--) {
            digits[i] =(digits[i]+1) %10;
            if(digits[i] !=0){
                return  digits;
            }
        }
        digits =new int [len+1];
        digits[0] =1;
        return  digits;
    }
    /*合并两个数组
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int len1 =m-1;
        int len2 = n-1;
        int len = m+n-1;
        while(n>=0 &&m >=0){
            if(nums1[len1]>=nums2[len2]){
                nums1[len] =nums1[len1];
                len1--;
            }else{
                nums1[len]=nums2[len2];
                len2--;
            }
            len--;
        }
        while(len2>=0){
            nums1[len]=nums2[len2];
            len2--;
            len--;
        }
    }
    /*给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     */
    public int maxProfit(int[] prices) {
        int minPrices =prices[0];
        int maxPrices = 0;
        for (int i=0;i<prices.length;i++){
            if(minPrices>prices[i]){
                minPrices =prices[i];
            } else if( maxPrices<prices[i] - minPrices){
                maxPrices =prices[i]-minPrices;
            }
        }
        return  maxPrices;
    }

    public static void main2(String[] args) {
        String s1="abc"+"def";//1
        String s2=new String(s1);//2
        if(s1.equals(s2))//3
            System.out.println(".equals succeeded");//4
        if(s1==s2)//5
            System.out.println("==succeeded");//6
    }
    /*
    统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

请注意，你可以假定字符串里不包括任何不可打印的字符。
     */
    public int countSegments(String s) {
        int n =s.length();
        int ans =0;
        for (int i = 0; i < n; i++) {
            if(s.charAt(i)==' '&&i++>=0) continue;;
            while(s.charAt(i)>=' ' && i<n){
                i++;
                ans++;
            }
        }
        return ans;
    }
   /* 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

    你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间*/
   public int singleNumber(int[] nums){
       int x=0;
       for(int num:nums){
           x^=num;//遍历nums进行异或运算
       }
       return x;//返回只出现一次的数字
   }
   /*
   给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。
    */
   public int majorityElement(int[] nums) {
       int x =0;
       int votes =0;
       for (int num :nums){
           if(votes==0){
               x=num;
           }
           votes += num==x?1:-1;
       }
       return x;
   }
   /*
   给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；
   如果数组中每个元素互不相同，返回 false 。
    */
   public boolean containsDuplicate(int[] nums) {
       Arrays.sort(nums);
       for (int i = 0; i < nums.length-1; i++) {
           if(nums[i] ==nums[i+1]){
               return true;
           }
       }
       return false;
   }

    public static void main3(String[] args) {
        int [] arr ={1,2,3,4,5,6};
        System.out.println(arr[arr[0]]);
        System.out.println(arr[1]+1);
        System.out.println(arr[1+1]);
    }
    /*
    设备中存有 n 个文件，文件 id 记于数组 documents。
    若文件 id 相同，则定义为该文件存在副本。请返回任一存在副本的文件 id。
     */
    public int findRepeatDocument(int[] documents) {
       int i=0;
       while(i<documents.length){
           if(documents[i]==i){
               i++;
               continue;
           }
           if(documents[documents[i]]==documents[i]){
               return documents[i];
           }
           int tmp =documents[i];
           documents[i] = documents[tmp];
           documents[tmp] =tmp;
       }
       return -1;
    }
    //汇总区间
    /*
    给定一个  无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。
也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，
并且不存在属于某个范围但不属于 nums 的数字 x 。
     */
    public List<String> summaryRanges(int[] nums) {
        List <String> list =new ArrayList<>();
        int left =0,right=0;
        int n =nums.length;
        while(right<n){
            while(right<n-1&&nums[right]+1==nums[right+1]){
                right++;
            }if(left==right){
                list.add(Integer.toString(nums[left]));
            }else{
                list.add(nums[left]+"->"+nums[right]);
            }
            right++;
            left=right;
        }
        return  list;
    }
}


